// https://leetcode.cn/problems/minimum-path-sum/

// 题干：给定一个包含非负整数的 m x n 网格 grid ，
//      请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
//      说明：每次只能向下或者向右移动一步。

// 示例：输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
//      输出：7

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int minPathSum(vector<vector<int>>& grid)
    {
        // 1.状态表示
        // dp[i][j]表示到达i，j位置时候，最小路径和
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = dp[1][0] = 0;

        // 2.状态转移方程
        // dp[i][j]要么从[i-1][j] 或者 [i][j - 1]的最小值
        // dp[i][j]=min(dp[i-1][j],dp[i][j-1])+g[i][j]
        for (int i = 1 ; i <= m ; i++)
            for (int j = 1 ; j <= n ; j++)
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];

        return dp[m][n];
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}};

    cout << sol.minPathSum(grid) << endl;
    
    return 0;
}